1. Field of the Invention
This invention relates to a method and apparatus for extracting contour lines from a pattern obtained in image processing technology. More particularly, this invention relates to a method and apparatus for obtaining the contour lines in real-time and provides a method wherein procedures can be partly incorporated into hardware.
2. Description of the Prior Art
With progress in image processing technology, its application fields are widely expanded into the fields of handling or inspecting an object image, or recognizing a character contour lines of an object image are extracted and distinguished from a pattern formed by an inputted signal obtained from a TV camera or the like source.
In image processing, the picture image is decomposed into small picture elements (picture element is abbreviated as a pixel) forming a matrix. The information related to each pixel is stored in a memory unit in the form of a "word". Each word has a specified word length including address information in rectanglar coordinates, multi gray level information (brightness or density level of each pixel having a multi-level magnitude) of 3 to 8 bits, and primary color information of red, green and blue. However, the present invention is related to the processing techniques solely on extracting the contours of an image, therefore, only a black and white image is dealt with. In the present invention, multi gray levels such as having more than 10 levels are dealt with in image processing. Because it is very easy to extract pattern contours from an image, formed with a binary level (only black or white level), the processing of the binary level image is excluded from the present invention.
As a method of extracting pattern contour, several methods are utilized in the prior art.
(1). The pattern is first processed into a binary code, and then the edge boundary thereof is extracted. This method has a merit of high speed, however, it is difficult to select the appropriate threshold value for binary coding of the pattern.
(2) The pattern is checked whether a pixel has a large change in density or gray level among neighboring pixels or not, and when the pixel is found to have a large change, the pixel is discriminated as being on the contour line. This method has a demerit of forming many broken off contours.
(3) The pattern is subjected to Gauss Laplacian processing (a kind of finding a second derivative of the gray level of each pixel), and when the pixel is found to have a sign change with regard to neighboring pixels, the pixel is regarded as being on the contour line. The accuracy is very good, however, this method requires a large scale computer system.
(4) The pattern is checked whether a pixel has a maximum level in the direction of its gray level gradient. The accuracy is very good, however, this method requires a lot of time in processing.
Among the above methods of the prior art, method (4) is very advantageous in accuracy and hardware-scale when the processing speed is improved. The reason for requiring a lot of time exists in that this method of extracting pattern contours mainly depends on the software technology, i.e. complexities of its algorithm. The details of the algorithm of this method are explained further.
FIG. 1 illustrates partly a gray level distribution stored in a memory for a matrix of pixels arranged in two-dimensional coordinates X and Y. For the sake of convenience, the coordinates of each pixel are expressed by X1 to X6 and Y1 to Y5, and the numeral entered in the square represents the gray level of each pixel. In order to extract pattern contours from the image of FIG. 1, process flows, for example, are shown by a block diagram of FIG. 2. Image data, which are stored in a memory unit in image input section 1 consisting of a plurality of address and gray level information, are subjected to X-direction differential calculator 31x and Y-direction differential calculator 31y, where gray level differentials Dx and Dy and X and Y directions are calculated. These component data Dx, Dy are combined and inputted to two component calculators of a vector, because the gray level gradient forms a vector (a word "gradient" is used instead of differential because a vector is dealt with). Two component calculators consist of gradient magnitude calculator 32 and gradient direction calculator 33, where components Fp and Gp of the gray level gradient vector can be obtained. The data are inputted to contour extractor 34, where calculations are carried out for each pixel by comparing its gray level data with those of adjacent pixels. The comparison of gray level gradients is carried out in a direction of the gray level gradient vector, and when the pixel is found to have a maximum gray level gradient, this pixel is regarded as one forming pattern contour and is distinguished from others.
Details of the above steps are explained further using FIG. 3. To explain calculation of Dx and Dy in X-direction differential calculator 31x and Y-direction differential calculator 3y of FIG. 2, an array of 3.times.3 pixels, 8 pixels being denoted as 00-22 and surrounding pixel P in X, Y coordinates, is taken into consideration. When the gray level of each pixel is denoted as L.sub.00 -L.sub.22, then the the gray level differentials Dx and Dy in X and Y directions of pixel P are assumed to have the values calculated by the following equations: EQU Dx=(L.sub.22 +L.sub.12 +L.sub.02 -L.sub.20 -L.sub.10 -L.sub.00)/3, EQU Dy=(L.sub.22 +L.sub.21 +L.sub.20 -L.sub.02 -L.sub.01 -L.sub.00)/3.
The values of Dx and Dy obtained by the above equations show the average X and Y direction differentials respectively, both differentials being sought between two groups of pixels located on both sides of pixel P. These values Dx and Dy are used as the components forming the gray level gradient of pixel P.
The gray level gradient is a quantity having magnitude and direction, forming a vector. Therefore, it is necessary to find out the absolute magnitude and direction of the gray level gradient vector, denoted as Fp and Gp.
Magnitude Fp can be obtained in gray level gradient calculator 32 using the following relation: EQU Fp=(Dx.sup.2 +Dy.sup.2).sup.1/2.
And further, direction Gp of the gray level gradient can be calculated in gradient direction calculator 33 using the following equations: EQU Gp=Cos.sup.-1 (Dx/Fp)
where Dy.gtoreq.0, EQU Gp=-Cos.sup.-1 (Dx/Fp)
where Dy&lt;0.
To extract contour lines, it is necessary to perform the above calculation for each pixel, which has Fp magnitude greater than a specified value. On the contrary, for the pixel which has a smaller Fp magnitude than specified, particularly selected numeals such as 999, or the like are outputted, and such pixels are regarded as irrelevant pixels for the pattern contour. In this way, Fp and Gp values for each pixel are calculated in gray level gradient calculator 32 and gradient direction calculator 33 one by one sequentially.
Thereafter utilizing the following algorithm, the pixels which form the pattern contour are selected and other pixels unsuitable for forming pattern contour are excluded in contour extractor 34.
In contour extractor 34, Gp data are first grouped into eight groups by direction as shown in FIG. 4. The circumference is equally divided in to 8 arcs, references a, b, c, and d are given to each arc, and two arcs located on opposite sides of the origin are given the same references. The area banded by two radii and the arc such as a, b, c, or d is subject to investigation, and such an area is referred to as sector a, b, c, or d respectively. The positive direction of the X-axis is taken as the reference, each sector is defined by the following conditions:
sector a; .pi./8&gt;Gp.gtoreq.-.pi./8, and the region further rotated by an angle .pi.,
sector b; 3.pi./8&gt;Gp.gtoreq..pi./8, and the region further rotated by an angle .pi.,
sector c; 5.pi./8&gt;Gp.gtoreq.3.pi./8, and the region further rotated by an angle .pi., and
sector c; 7.pi./8&gt;Gp.gtoreq.5.pi./8, and the region further rotated by an angle .pi..
Depending on which sector the gray level gradient vector Gp is contained in, one of the following discriminating conditions is applied. The pixel satisfying the following conditions is regarded as one of pixels forming pattern contour.
(1) When Gp is contained in sectors a, the following two conditions are satisfied: EQU Fp(x,y).gtoreq.Fp(x-1,y), and EQU Fp(x,y).gtoreq.Fp(x+1,y).
(2) When Gp is contained in sectors b, the following two conditions are satisfied: EQU Fp(x,y).gtoreq.Fp(x+1,y+1), and EQU Fp(x,y).gtoreq.Fp(x-1,y-1).
(3) When Gp is contained in sectors c, the following two conditions are satisfied: EQU Fp(x,y).gtoreq.Fp(x,y+1), and EQU Fp(x,y).gtoreq.Fp(x,y-1).
(4) When Gp is contained in sectors d, the following two conditions are satisfied: EQU Fp(x,y).gtoreq.Fp(x+1,y-1), and EQU Fp(x,y).gtoreq.Fp(x-1,y+1).
Each group of the above conditions determines whether or not the gray level magnitude Fp for pixel P in process of FIG. 3 has a maximum value among the three pixels along its gradient direction Gp. If Fp is found to be maximum, the pixel P is judged to be on the pattern contour.
For example, the pixel located at the coordinate (X3,Y3) of FIG. 1 shows that Gp thereof has the direction shown by the arrow and the gray level magnitudes of two adjacent pixels (X2,Y4) and (X4,Y2) along the arrow are less than that of pixel P(X3,Y3). Therefore pixel P is judged to be one of pixels forming the pattern contour.
In the above explanation, the comparison to find out the maximum value is performed with two adjoining pixels. However, in the practical application, the comparison is performed usually among five to seven neighboring pixels for more accuracy. This is schematically illustrated in FIGS. 5 and 6. Each arrow is assumed to show the magnitude and direction of the gray level gradient vector corresponding to each pixel. In FIG. 5, when vector p is compared with four vectors a to d, it is found that vector b is maximum and vector p is less than vector p. Therefore, vector p is indicates that this pixel is not on the pattern contour. In the same way, when vector p' is compared with four vectors a' to d', vector p' is found to be maximum and therefore indicates that the pixel is on the pattern contour.
In this way, all pixels are subjected to discrimination procedures and finally, marked pixels of FIG. 6 forming the pattern contour are extracted.
In order to extract the pattern contours, the procedures are repeated for all pixels following the above algorithm. The discriminated pixels form the pattern contours. The procedures are written in a program form and executed under the program control. However, the above noted procedure require a lot of process time and are not suitable for extracting pattern contours in real-time process. Therefore, it is required that some parts of the procedures are incorporated into a hardware as much as possible in order to obtain a higher speed of processing.